Insertion Sort - O(N^2) - Segments List to Parts¶
This algorithm Segments the List into two parts: Sorted and Unsorted.
It iterates over the Unsorted Segment, and inserts the element being viewed
into the CORRECT POSITION of the Sorted List.
Explanation:
We assume that the first element of the list is sorted.
We then go to the next element, let’s call it x.
If x is larger than the first element we leave as is.
If x is smaller, we copy the value of the first element to the second position
and then set the first element to x.
As we go to the other elements of the unsorted segment, we continuously move Larger Elements
in the Sorted Segment up the List until we encounter an element smaller than x
or reach the end of the sorted segment, and then place x in it’s correct position.
Time Complexity:
In the worst case scenario, an array would be sorted in reverse order.
The outer for loop in the Insertion Sort function always iterates N-1 times.
In the worst case scenario, the inner for loop would swap once,
then swap two and so forth. The amount of swaps would then be
1 + 2 + … + (N - 3) + (N - 2) + (N - 1)
which gives the Insertion Sort a time complexity of
O(N^2).
Sample Data:
[14, 46, 43, 27, 57, 41, 45, 21, 70]
Expected Result:
[14, 21, 27, 41, 43, 45, 46, 57, 70]
def insertionSort(L):
# Start on the second element as we assume the first element is sorted
for i in range(1, len(L)):
item_to_insert = L[i]
# And keep a reference of the index of the previous element
pos = i - 1
# Move all items of the Sorted Segment Forward
# if they are Larger than the item to insert
while pos >= 0 and L[pos] > item_to_insert:
L[pos + 1] = L[pos]
pos -= 1
# Insert the item
L[pos + 1] = item_to_insert
Test:
LON = [14, 46, 43, 27, 57, 41, 45, 21, 70]
insertionSort(LON)
print(LON)
Output:
[14, 21, 27, 41, 43, 45, 46, 57, 70]